{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Good Days to Rob the Bank"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: goodDaysToRobBank"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #适合野炊的日子"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你和朋友们准备去野炊。给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>security</code>&nbsp;，其中&nbsp;<code>security[i]</code>&nbsp;是第 <code>i</code>&nbsp;天的建议出行指数。日子从 <code>0</code>&nbsp;开始编号。同时给你一个整数&nbsp;<code>time</code>&nbsp;。</p>\n",
    "\n",
    "<p>如果第 <code>i</code>&nbsp;天满足以下所有条件，我们称它为一个适合野炊的日子：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>第 <code>i</code>&nbsp;天前和后都分别至少有 <code>time</code>&nbsp;天。</li>\n",
    "\t<li>第 <code>i</code>&nbsp;天前连续 <code>time</code>&nbsp;天建议出行指数都是非递增的。</li>\n",
    "\t<li>第 <code>i</code>&nbsp;天后连续 <code>time</code>&nbsp;天建议出行指数都是非递减的。</li>\n",
    "</ul>\n",
    "\n",
    "<p>更正式的，第 <code>i</code> 天是一个适合野炊的日子当且仅当：<code>security[i - time] &gt;= security[i - time + 1] &gt;= ... &gt;= security[i] &lt;= ... &lt;= security[i + time - 1] &lt;= security[i + time]</code>.</p>\n",
    "\n",
    "<p>请你返回一个数组，包含 <strong>所有</strong> 适合野炊的日子（下标从 <strong>0</strong>&nbsp;开始）。返回的日子可以 <strong>任意</strong>&nbsp;顺序排列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>security = [5,3,3,3,5,6,2], time = 2\n",
    "<b>输出：</b>[2,3]\n",
    "<strong>解释：</strong>\n",
    "第 2 天，我们有 security[0] &gt;= security[1] &gt;= security[2] &lt;= security[3] &lt;= security[4] 。\n",
    "第 3 天，我们有 security[1] &gt;= security[2] &gt;= security[3] &lt;= security[4] &lt;= security[5] 。\n",
    "没有其他日子符合这个条件，所以日子 2 和 3 是适合野炊的日子。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>security = [1,1,1,1,1], time = 0\n",
    "<b>输出：</b>[0,1,2,3,4]\n",
    "<strong>解释：</strong>\n",
    "因为 time 等于 0 ，所以每一天都是适合野炊的日子，所以返回每一天。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>security = [1,2,3,4,5,6], time = 2\n",
    "<b>输出：</b>[]\n",
    "<strong>解释：</strong>\n",
    "没有任何一天的前 2 天建议出行指数是非递增的。\n",
    "所以没有适合野炊的日子，返回空数组。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= security.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= security[i], time &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-good-days-to-rob-the-bank](https://leetcode.cn/problems/find-good-days-to-rob-the-bank/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-good-days-to-rob-the-bank](https://leetcode.cn/problems/find-good-days-to-rob-the-bank/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,3,3,3,5,6,2]\\n2', '[1,1,1,1,1]\\n0', '[1,2,3,4,5,6]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        if time == 0:\n",
    "            return list(range(n))\n",
    "        g = [0] * n\n",
    "        for i in range(1, n):\n",
    "            if security[i] > security[i - 1]:\n",
    "                g[i] = 1\n",
    "            elif security[i] < security[i - 1]:\n",
    "                g[i] = -1\n",
    "        sum_a = 0\n",
    "        sum_b = 0\n",
    "        a = [0] * n\n",
    "        b = [0] * n\n",
    "        for i in range(n):\n",
    "            if g[i] == 1:\n",
    "                sum_a += 1\n",
    "            if g[i] == -1:\n",
    "                sum_b += 1\n",
    "            a[i] = sum_a\n",
    "            b[i] = sum_b\n",
    "        ans = []\n",
    "        for i in range(time, n - time):\n",
    "            if a[i] - a[i - time] == 0 and b[i + time] - b[i] == 0:\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, a: List[int], time: int) -> List[int]:\n",
    "        n = len(a)\n",
    "        left = [0] * n\n",
    "        left[0] = 1\n",
    "        for i in range(1, n):\n",
    "            if a[i] <= a[i - 1]:\n",
    "                left[i] = left[i - 1] + 1\n",
    "            else:\n",
    "                left[i] = 1\n",
    "        right = 1\n",
    "        ret = []\n",
    "        if 1 > time and left[n - 1] > time:\n",
    "            ret.append(n - 1)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if a[i] <= a[i + 1]:\n",
    "                right += 1\n",
    "            else:\n",
    "                right = 1\n",
    "            if right > time and left[i] > time:\n",
    "                ret.append(i)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        i, j = 1, 1\n",
    "        cnt1, cnt2 = 0, 0\n",
    "        ans = [] \n",
    "        if time == 0:\n",
    "            return [i for i in range(n)]\n",
    "\n",
    "        while i < n and j < n:\n",
    "            while i < n and cnt1 < time:\n",
    "                if security[i] <= security[i-1]:\n",
    "                    i += 1\n",
    "                    cnt1 += 1\n",
    "                else:\n",
    "                    break \n",
    "\n",
    "            if cnt1 == time:\n",
    "                j = max(j, i)\n",
    "                while j < n and cnt2 < time:\n",
    "                    if security[j] >= security[j-1]:\n",
    "                        j += 1\n",
    "                        cnt2 += 1\n",
    "                    else:\n",
    "                        break \n",
    "                if cnt2 == time:\n",
    "                    ans.append(i-1)\n",
    "                    cnt1 -= 1\n",
    "                    cnt2 -= 1\n",
    "                else:\n",
    "                    if j == i:\n",
    "                        i+=1\n",
    "                    else:\n",
    "                        cnt1, cnt2 =0, 0 \n",
    "                        i = j \n",
    "            else:\n",
    "                #print(i, cnt1)\n",
    "                cnt1, cnt2 = 0, 0 \n",
    "                i += 1\n",
    "            \n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        R = [1] * n\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if security[i] <= security[i+1]:\n",
    "                R[i] = R[i+1] + 1\n",
    "        result = []\n",
    "        prev = -1\n",
    "        max_len = 0\n",
    "        for i, num in enumerate(security):\n",
    "            if num <= prev:\n",
    "                max_len += 1\n",
    "            else:\n",
    "                max_len = 1\n",
    "            if max_len > time and R[i] > time:\n",
    "                result.append(i)\n",
    "            prev = num\n",
    "        return result\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        suf = [1] * n\n",
    "        # 倒序 非递增的\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if security[i] <= security[i+1]:\n",
    "                suf[i] = suf[i+1] + 1\n",
    "        # 正序 非递增\n",
    "        pre = 1\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            if i > 0 and security[i] <= security[i-1]:\n",
    "                pre+=1\n",
    "            else:\n",
    "                pre = 1\n",
    "            if pre>=time+1 and suf[i]>=time+1:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, ss: List[int], t: int) -> List[int]:       \n",
    "        q=[0]\n",
    "        n=len(ss)\n",
    "        pr=ss[0]\n",
    "        i=1\n",
    "        for x in ss[1:]:\n",
    "            if x<=pr:\n",
    "               q.append(q[-1])\n",
    "            else:\n",
    "               q.append(i)\n",
    "            i+=1\n",
    "            pr=x\n",
    "        e=[n-1]\n",
    "        pr=ss[n-1]\n",
    "        i=n-2   \n",
    "        for x in ss[:-1][::-1]:\n",
    "           if x<=pr:\n",
    "            e.append(e[-1])\n",
    "           else:\n",
    "            e.append(i)\n",
    "           pr=x \n",
    "           i-=1\n",
    "        e=e[::-1]\n",
    "        ans=[]\n",
    "        for i in range(n):        \n",
    "           if i-q[i]>=t and e[i]-i>=t:\n",
    "              ans.append(i)\n",
    "        print(q,e)      \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#  5  3  3  3  5  6  2 \n",
    "#  0 -1  0  0. 1. 1. -1\n",
    "#  0  0. 0  0. 1. 2. 3.   1的和\n",
    "#  0。1。 1。1。1  1。 2。  -1的和\n",
    "#        \n",
    "# 后>前 递增 为1， 后<前 递减 为-1， 要求左边递减，右边递增\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        diffs = [0]\n",
    "        for i in range(0, len(security) - 1):\n",
    "            if security[i+1] - security[i] > 0:\n",
    "                diffs.append(1)\n",
    "            elif security[i+1] - security[i] == 0:\n",
    "                diffs.append(0)\n",
    "            else:\n",
    "                diffs.append(-1)\n",
    "        pre_1 = [0] * len(security)\n",
    "        pre_minus_1 = [0] * len(security)\n",
    "        for i in range(0, len(security)):\n",
    "            if i == 0:\n",
    "                pre_1[0] = diffs[i] == 1\n",
    "                pre_minus_1[0] == diffs[i] == -1\n",
    "            else:\n",
    "                pre_1[i] = pre_1[i-1] + (diffs[i] == 1)\n",
    "                pre_minus_1[i] = pre_minus_1[i-1] + (diffs[i] == -1)\n",
    "        ans = []\n",
    "        for i in range(time, len(security) - time):\n",
    "            sum_left = pre_1[i] - pre_1[i - time]\n",
    "            sum_right = pre_minus_1[i+time] - pre_minus_1[i]\n",
    "            if sum_left == 0 and sum_right == 0:\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#  5  3  3  3  5  6  2 \n",
    "#  0 -1  0  0. 1. 1. -1\n",
    "# 后>前 递增 为1， 后<前 递减 为-1\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        diffs = [0]\n",
    "        for i in range(0, len(security) - 1):\n",
    "            if security[i+1] - security[i] > 0:\n",
    "                diffs.append(1)\n",
    "            elif security[i+1] - security[i] == 0:\n",
    "                diffs.append(0)\n",
    "            else:\n",
    "                diffs.append(-1)\n",
    "        pre_1 = [0] * (len(security) + 1)\n",
    "        pre_minus_1 = [0] * (len(security) + 1)\n",
    "        for i in range(1, len(security)+1):\n",
    "            pre_1[i] = pre_1[i-1] + (diffs[i-1] == 1)\n",
    "            pre_minus_1[i] = pre_minus_1[i-1] + (diffs[i-1] == -1)\n",
    "        ans = []\n",
    "        for i in range(time, len(security) - time):\n",
    "            sum_left = pre_1[i+1] - pre_1[i+1 - time]\n",
    "            sum_right = pre_minus_1[i+1+time] - pre_minus_1[i+1]\n",
    "            if sum_left == 0 and sum_right == 0:\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        # n=len(security)\n",
    "        # if time==0:\n",
    "        #     return [i for i in range(n)]\n",
    "        # dp=[False for _ in range(n)]\n",
    "        # dp1=[0]*n\n",
    "        # for i in range(1,n):\n",
    "        #     if security[i]<=security[i-1]:\n",
    "        #         dp1[i]=dp1[i-1]+1\n",
    "        #     else:\n",
    "        #         dp1[i]=0\n",
    "        # dp2=[0]*n\n",
    "        # for i in range(n-2,-1,-1):\n",
    "        #     if security[i]<=security[i+1]:\n",
    "        #         dp2[i]=dp2[i+1]+1\n",
    "        #     else:\n",
    "        #         dp2[i]=0\n",
    "        # for i in range(time,n-time):\n",
    "        #     if dp1[i]>=time and dp2[i]>=time:\n",
    "        #         dp[i]=True\n",
    "        # return [ i for i in range(n) if dp[i]]\n",
    "        n = len(security)\n",
    "        g = [0] * n\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            if security[i] == security[i - 1]:\n",
    "                continue\n",
    "            g[i] = 1 if security[i] >= security[i - 1] else -1\n",
    "        \n",
    "        a = [0] * (n + 1)\n",
    "        b = [0] * (n + 1)\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            a[i] = a[i - 1] + (1 if g[i - 1] == 1 else 0)\n",
    "            b[i] = b[i - 1] + (1 if g[i - 1] == -1 else 0)\n",
    "        \n",
    "        ans = []\n",
    "        for i in range(time, n - time):\n",
    "            c1 = a[i + 1] - a[i + 1 - time]\n",
    "            c2 = b[i + 1 + time] - b[i + 1]\n",
    "            if c1 == 0 and c2 == 0:\n",
    "                ans.append(i)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, nums: List[int], k: int) -> List[int]:\n",
    "        ans = []\n",
    "        left = right = 0\n",
    "        if k + k >= len(nums): return ans\n",
    "        if k == 0:\n",
    "            return [i for i in range(len(nums)) ]\n",
    "\n",
    "        for i in range(k):\n",
    "            left  += nums[i] >= nums[i+1]\n",
    "            right += nums[i+k] <= nums[i+k+1]\n",
    "        if left == right == k:\n",
    "            ans.append(k)\n",
    "\n",
    "        for i in range(k + 1, len(nums) - k):\n",
    "            left  += nums[i-1] >= nums[i]\n",
    "            right -= nums[i-1] <= nums[i]\n",
    "            left  -= nums[i-k-1] >= nums[i-k]\n",
    "            right += nums[i+k-1] <= nums[i+k]\n",
    "            if left == k == right:\n",
    "                ans.append(i)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        # n=len(security)\n",
    "        # if time==0:\n",
    "        #     return [i for i in range(n)]\n",
    "        # dp=[False for _ in range(n)]\n",
    "        # dp1=[0]*n\n",
    "        # for i in range(1,n):\n",
    "        #     if security[i]<=security[i-1]:\n",
    "        #         dp1[i]=dp1[i-1]+1\n",
    "        #     else:\n",
    "        #         dp1[i]=0\n",
    "        # dp2=[0]*n\n",
    "        # for i in range(n-2,-1,-1):\n",
    "        #     if security[i]<=security[i+1]:\n",
    "        #         dp2[i]=dp2[i+1]+1\n",
    "        #     else:\n",
    "        #         dp2[i]=0\n",
    "        # for i in range(time,n-time):\n",
    "        #     if dp1[i]>=time and dp2[i]>=time:\n",
    "        #         dp[i]=True\n",
    "        # return [ i for i in range(n) if dp[i]]\n",
    "        n = len(security)\n",
    "        g = [0] * n\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            if security[i] == security[i - 1]:\n",
    "                continue\n",
    "            g[i] = 1 if security[i] >= security[i - 1] else -1\n",
    "        \n",
    "        a = [0] * (n + 1)\n",
    "        b = [0] * (n + 1)\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            a[i] = a[i - 1] + (1 if g[i - 1] == 1 else 0)\n",
    "            b[i] = b[i - 1] + (1 if g[i - 1] == -1 else 0)\n",
    "        \n",
    "        ans = []\n",
    "        for i in range(time, n - time):\n",
    "            c1 = a[i + 1] - a[i + 1 - time]\n",
    "            c2 = b[i + 1 + time] - b[i + 1]\n",
    "            if c1 == 0 and c2 == 0:\n",
    "                ans.append(i)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        # n=len(security)\n",
    "        # if time==0:\n",
    "        #     return [i for i in range(n)]\n",
    "        # dp=[False for _ in range(n)]\n",
    "        # dp1=[0]*n\n",
    "        # for i in range(1,n):\n",
    "        #     if security[i]<=security[i-1]:\n",
    "        #         dp1[i]=dp1[i-1]+1\n",
    "        #     else:\n",
    "        #         dp1[i]=0\n",
    "        # dp2=[0]*n\n",
    "        # for i in range(n-2,-1,-1):\n",
    "        #     if security[i]<=security[i+1]:\n",
    "        #         dp2[i]=dp2[i+1]+1\n",
    "        #     else:\n",
    "        #         dp2[i]=0\n",
    "        # for i in range(time,n-time):\n",
    "        #     if dp1[i]>=time and dp2[i]>=time:\n",
    "        #         dp[i]=True\n",
    "        # return [ i for i in range(n) if dp[i]]\n",
    "\n",
    "        n = len(security)\n",
    "        if time==0:\n",
    "            return [i for i in range(n)]\n",
    "        pre_max=[0]*n\n",
    "        for i in range(1,n):\n",
    "            if security[i]>security[i-1]:\n",
    "                pre_max[i]=1\n",
    "            elif security[i]<security[i-1]:\n",
    "                pre_max[i]=-1\n",
    "            else:\n",
    "                pre_max[i]=0\n",
    "        print(pre_max)\n",
    "        a=[0]*(n+1)#前缀为1\n",
    "        b=[0]*(n+1)#前缀为-1\n",
    "        for i in range(1,n+1):\n",
    "            a[i]=a[i-1]+(1 if pre_max[i-1]==1 else 0)\n",
    "            b[i]=b[i-1]+(1 if pre_max[i-1]==-1 else 0)\n",
    "        print(a,b)\n",
    "        res=[]\n",
    "        for i in range(time,n-time):\n",
    "            c1=a[i+1]-a[i-time+1]\n",
    "            c2=b[i+time+1]-b[i+1]\n",
    "            if c1==c2==0:res.append(i)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        down_stack = []\n",
    "        left = [False for _ in security]\n",
    "        for i in range(len(security)):\n",
    "            if time == 0:\n",
    "                left[i] = True\n",
    "            elif len(down_stack) >= time and down_stack[-time] == i-time and security[i] <= security[down_stack[-1]]:\n",
    "                left[i] = True\n",
    "            while down_stack and security[down_stack[-1]] < security[i]:\n",
    "                down_stack.pop()\n",
    "            down_stack.append(i)\n",
    "\n",
    "        down_stack = []\n",
    "        right = [False for _ in security]\n",
    "        for i in range(len(security)-1, -1, -1):\n",
    "            if time == 0:\n",
    "                right[i] = True\n",
    "            elif len(down_stack) >= time and down_stack[-time] == i+time and security[i] <= security[down_stack[-1]]:\n",
    "                right[i] = True\n",
    "            while down_stack and security[down_stack[-1]] < security[i]:\n",
    "                down_stack.pop()\n",
    "            down_stack.append(i)\n",
    "        res = []\n",
    "        for i in range(len(left)):\n",
    "            if left[i] and right[i]:\n",
    "                res.append(i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        # n=len(security)\n",
    "        # if time==0:\n",
    "        #     return [i for i in range(n)]\n",
    "        # dp=[False for _ in range(n)]\n",
    "        # dp1=[0]*n\n",
    "        # for i in range(1,n):\n",
    "        #     if security[i]<=security[i-1]:\n",
    "        #         dp1[i]=dp1[i-1]+1\n",
    "        #     else:\n",
    "        #         dp1[i]=0\n",
    "        # dp2=[0]*n\n",
    "        # for i in range(n-2,-1,-1):\n",
    "        #     if security[i]<=security[i+1]:\n",
    "        #         dp2[i]=dp2[i+1]+1\n",
    "        #     else:\n",
    "        #         dp2[i]=0\n",
    "        # for i in range(time,n-time):\n",
    "        #     if dp1[i]>=time and dp2[i]>=time:\n",
    "        #         dp[i]=True\n",
    "        # return [ i for i in range(n) if dp[i]]\n",
    "\n",
    "        n = len(security)\n",
    "        # if time==0:\n",
    "        #     return [i for i in range(n)]\n",
    "        pre_max=[0]*n\n",
    "        for i in range(1,n):\n",
    "            if security[i]>security[i-1]:\n",
    "                pre_max[i]=1\n",
    "            elif security[i]<security[i-1]:\n",
    "                pre_max[i]=-1\n",
    "            else:\n",
    "                pre_max[i]=0\n",
    "        print(pre_max)\n",
    "        a=[0]*(n+1)#前缀为1\n",
    "        b=[0]*(n+1)#前缀为-1\n",
    "        for i in range(1,n+1):\n",
    "            a[i]=a[i-1]+(1 if pre_max[i-1]==1 else 0)\n",
    "            b[i]=b[i-1]+(1 if pre_max[i-1]==-1 else 0)\n",
    "        print(a,b)\n",
    "        res=[]\n",
    "        for i in range(time,n-time):\n",
    "            c1=a[i+1]-a[i-time+1]\n",
    "            c2=b[i+time+1]-b[i+1]\n",
    "            if c1==c2==0:res.append(i)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        if time == 0:\n",
    "            return [i for i in range(n)]\n",
    "        down_set = set()\n",
    "        down_count = 0\n",
    "        up_set = set()\n",
    "        up_count = 0\n",
    "        for i in range(1, n):\n",
    "            if security[i] <= security[i-1]:\n",
    "                down_count += 1\n",
    "            else:\n",
    "                down_count = 0\n",
    "            if down_count >= time:\n",
    "                down_set.add(i)\n",
    "            \n",
    "            if security[n-i-1] <= security[n-i]:\n",
    "                up_count += 1\n",
    "            else:\n",
    "                up_count = 0\n",
    "            if up_count >= time:\n",
    "                up_set.add(n-i-1)\n",
    "        return list(down_set.intersection(up_set))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        \n",
    "        res = []\n",
    "        pre_cond = []\n",
    "        post_cond = []\n",
    "        if time > len(security):\n",
    "            return res\n",
    "        \n",
    "        if len(security) <= 2*time:\n",
    "            return res\n",
    "        \n",
    "        if time==0:\n",
    "            return list(range(len(security)))\n",
    "        \n",
    "        l, r = 0, 0\n",
    "        while r < len(security):\n",
    "            if l==r:\n",
    "                r+=1\n",
    "            elif security[r-1]>=security[r]:\n",
    "                if r - l >=time:\n",
    "                    pre_cond.append(r)\n",
    "                    l+=1\n",
    "                r+=1\n",
    "            else:\n",
    "                l=r\n",
    "    \n",
    "        \n",
    "        l, r = 0, 0\n",
    "        while r < len(security):\n",
    "            if l==r:\n",
    "                r+=1\n",
    "            elif security[r-1]<=security[r]:\n",
    "                if r - l >=time:\n",
    "                    post_cond.append(l)\n",
    "                    l+=1\n",
    "                r+=1\n",
    "            else:\n",
    "                l=r\n",
    "\n",
    "\n",
    "        res = list(set(pre_cond)&set(post_cond))\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        if n==1:\n",
    "            return [0] if time==0 else []\n",
    "        if n<2*time+1: return []\n",
    "        right_up = [0]*n\n",
    "        left_down = [0]*n\n",
    "        for i in range(1,n):\n",
    "            cur = security[i]\n",
    "            rur = security[n-i-1]\n",
    "            left_down[i] = 1+left_down[i-1] if cur<=security[i-1] else 0\n",
    "            right_up[n-i-1]=1+right_up[n-i] if rur<=security[n-i] else 0\n",
    "        \n",
    "        res = []\n",
    "        for i in range(time, n-time):\n",
    "            if left_down[i]>=time and right_up[i]>=time:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        # 尝试用单调找试一下\n",
    "        n = len(security)\n",
    "        if n < time * 2 + 1:\n",
    "            return []\n",
    "        stack = []\n",
    "        pre = [0] * n\n",
    "        pre[0] = 0\n",
    "        stack.append(security[0])\n",
    "        for i in range(1, n):\n",
    "            x = security[i]\n",
    "            if x > stack[-1]:\n",
    "                pre[i] = 0\n",
    "                stack.clear()\n",
    "                stack.append(x)\n",
    "            else:\n",
    "                stack.append(x)\n",
    "                pre[i] = len(stack) - 1\n",
    "        after = [0] * n\n",
    "        stack.clear()\n",
    "        stack.append(security[-1])\n",
    "        after[-1] = 0\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            x = security[i]\n",
    "            if x > stack[-1]:\n",
    "                after[i] = 0\n",
    "                stack.clear()\n",
    "                stack.append(x)\n",
    "            else:\n",
    "                stack.append(x)\n",
    "                after[i] = len(stack) - 1\n",
    "\n",
    "        #print(pre, after)\n",
    "\n",
    "        res = []\n",
    "        \n",
    "        \n",
    "        for i in range(time, n - time):\n",
    "            if pre[i] >= time and after[i] >= time:\n",
    "                res.append(i)\n",
    "\n",
    "        return res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        left = [0]*n\n",
    "        right = [0]*n\n",
    "        ans = []\n",
    "        for i in range(1,n):\n",
    "            if security[i] <= security[i-1]:\n",
    "                left[i] = left[i-1]+1\n",
    "            if security[n-i-1]<= security[n-i]:\n",
    "                right[n-i-1] = right[n-i] +1\n",
    "        for j in range(time,n-time):\n",
    "            if left[j] >= time and right[j] >= time:\n",
    "                ans.append(j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n= len(security)\n",
    "        left , right = [0] * n ,[0] * n\n",
    "        for i in range (1,n):\n",
    "            if security [i -1]>= security[i]:\n",
    "                left [i] = left [i-1] +1\n",
    "            if security [n-i] >= security [n - 1 -i]:\n",
    "                right[n - 1 - i] =right[n - i]+1\n",
    "        return [i for i in range(n) if left[i]>= time and right[i]>=time]        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        # 前后缀分解\n",
    "        # 前缀是到这天前面有几天递减 \n",
    "        # 后缀是到这天后面有几天递增\n",
    "        qian = [0]*len(security)\n",
    "        hou = [0]*len(security)\n",
    "        qian[0] = 1\n",
    "        for i in range(len(security)):\n",
    "            if security[i] <= security[i-1]:\n",
    "                qian[i] = qian[i-1] + 1\n",
    "            else:\n",
    "                qian[i] = 1\n",
    "        hou[len(security)-1] = 1\n",
    "        for i in range(len(security)-2,-1,-1):\n",
    "            if security[i] <= security[i+1]:\n",
    "                hou[i] = hou[i+1] + 1\n",
    "            else:\n",
    "                hou[i] = 1\n",
    "        res = []\n",
    "        for i in range(time,len(security)-time):\n",
    "            if qian[i]>time and hou[i]>time:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        left, right = [0] * n, [0] * n\n",
    "        for i in range(1, n):\n",
    "            if security[i - 1] >= security[i]:\n",
    "                left[i] = left[i - 1] + 1\n",
    "            if security[n - i] >= security[n - 1 - i]:\n",
    "                right[n - 1 - i] = right[n - i] + 1\n",
    "        return [i for i in range(n) if left[i] >= time and right[i] >= time]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        presum = [0] * n\n",
    "        postsum = [0] * n\n",
    "        for i in range(1 , n):\n",
    "            if security[i] <= security[i - 1]:\n",
    "                presum[i] = presum[i - 1] + 1\n",
    "            if security[n - i - 1] <= security[n - i]:\n",
    "                postsum[n - i - 1] = postsum[n - i] + 1\n",
    "        return [i for i in range(time , n - time) if presum[i] >= time and postsum[i] >= time]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        left , right = [0] * n,[0] * n\n",
    "        for i in range(1,n):\n",
    "            if security[i - 1] >= security[i]:\n",
    "                left[i] = left[i - 1] + 1\n",
    "            if security[n - i] >= security[n - 1 - i]:\n",
    "                right[n - 1 - i] = right[n - i] + 1\n",
    "        return [i for i in range(n) if left[i] >= time and right[i] >= time]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        down,up = [0]*n ,[0]*n \n",
    "        for i in range(1,n):\n",
    "            if security[i] <= security[i-1]:\n",
    "                down[i] = down[i-1] + 1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if security[i] <= security[i+1]:\n",
    "                up[i] = up[i+1] + 1\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if down[i] >=time and up[i] >= time:\n",
    "                ans.append(i)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        left = [0]*n\n",
    "        right = [0]*n\n",
    "        for i in range(1,n):\n",
    "            if security[i] <= security[i-1]:\n",
    "                left[i] = left[i-1]+1\n",
    "            if security[n-i] >= security[n-i-1]:\n",
    "                right[n-i-1] = right[n-i]+1\n",
    "        \n",
    "        return[j for j in range(time,n-time) if left[j]>=time and right[j] >= time]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n=len(security)\n",
    "        pre=[0]*n\n",
    "        post=[0]*n\n",
    "        for i in range(1,n):\n",
    "            if security[i]>=security[i-1]:\n",
    "                pre[i]=pre[i-1]+1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if security[i]>=security[i+1]:\n",
    "                post[i]=post[i+1]+1\n",
    "        ans=[]\n",
    "        for i in range(time,n-time):\n",
    "            if pre[i+time]-pre[i]==time and post[i-time]-post[i]==time:\n",
    "                ans.append(i)\n",
    "        return ans                        \n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        left = [1] * n\n",
    "        right = [1] * n\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            if security[i] <= security[i-1]:\n",
    "                left[i] += left[i-1]\n",
    "        \n",
    "        for i in range(n-2, -1, -1):\n",
    "            if security[i] <= security[i+1]:\n",
    "                right[i] += right[i+1]\n",
    "        \n",
    "        return [i for i, (x, y) in enumerate(zip(left, right)) if x > time and y > time]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        nums = security\n",
    "        answer_list = list()\n",
    "        nums_length = len(nums)\n",
    "        non_increasing_list = [1] * nums_length\n",
    "        non_decreasing_list = [1] * nums_length\n",
    "        for index in range(1, nums_length):\n",
    "            if nums[index] <= nums[index - 1]:\n",
    "                non_decreasing_list[index] = non_decreasing_list[index - 1] + 1\n",
    "        for index in range(nums_length - 2, -1, -1):\n",
    "            if nums[index] <= nums[index + 1]:\n",
    "                non_increasing_list[index] = non_increasing_list[index + 1] + 1\n",
    "        for index in range(time, nums_length - time):\n",
    "            if non_decreasing_list[index] >= time + 1 and non_increasing_list[index] >= time + 1:\n",
    "                answer_list.append(index)\n",
    "        return answer_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        left,right = [0 for i in range(len(security))],[0 for i in range(len(security))]\n",
    "        for i in range(len(security)-1):\n",
    "            if security[i] >= security[i+1]:\n",
    "                left[i+1] = 1\n",
    "        for i in range(len(security)-1,0,-1):\n",
    "            if security[i] >= security[i-1]:\n",
    "                right[i-1] = 1\n",
    "        for i in range(1,len(left)):\n",
    "            if left[i] == 1:\n",
    "                left[i] = left[i-1]+1\n",
    "            else:\n",
    "                left[i] = 0\n",
    "        for i in range(len(right)-2,-1,-1):\n",
    "            if right[i] == 1:\n",
    "                right[i] = right[i+1]+1\n",
    "            else:\n",
    "                right[i] = 0\n",
    "        res = []\n",
    "        for i in range(len(security)):\n",
    "            if left[i]>=time and right[i]>=time:\n",
    "                res.append(i)\n",
    "        return res\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        # 核心思想：预处理前后缀\n",
    "        # pre[i]表示到第i天非递增的天数（从前到后）\n",
    "        # suf[i]表示到第i天非递减的天数（从后到前）\n",
    "        n = len(security)\n",
    "        pre = [0]*(n)\n",
    "        suf = [0]*(n)\n",
    "        for i in range(1,n):\n",
    "            if security[i-1] >= security[i]:\n",
    "                pre[i] += pre[i-1]+1\n",
    "            if security[n-i-1] <= security[n-i]:\n",
    "                suf[n-i-1] = suf[n-i]+1\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if pre[i] >= time and suf[i] >= time:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        left = [0] * n\n",
    "        right = [0] * n\n",
    "        for i in range(1, n):\n",
    "            if security[i] <= security[i - 1]:\n",
    "                left[i] = left[i - 1] + 1\n",
    "            if security[n - i - 1] <= security[n - i]:\n",
    "                right[n - i - 1] = right[n - i] + 1\n",
    "        return [i for i in range(time, n - time) if left[i] >= time and right[i] >= time]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        left = [0] * n\n",
    "        right = [0] * n\n",
    "        for i in range(1, n):\n",
    "            if security[i] <= security[i - 1]:\n",
    "                left[i] = left[i - 1] + 1\n",
    "            if security[n - i - 1] <= security[n - i]:\n",
    "                right[n - i - 1] = right[n - i] + 1\n",
    "        return [i for i in range(time, n - time) if left[i] >= time and right[i] >= time]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        pre, after = [0] * n, [0] * n\n",
    "        for i in range(1, n):\n",
    "            if security[i] <= security[i-1]:\n",
    "                pre[i] = pre[i-1] + 1\n",
    "            if security[-i-1] <= security[-i]:\n",
    "                after[-i-1] = after[-i] + 1\n",
    "        return [i for i in range(n) if pre[i] >= time and after[i] >= time]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "        前缀后缀分解 \n",
    "        对于 i , a[i] >= time b[i] >= time 满足条件则i是合法的\n",
    "    '''\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        a = [0] * n\n",
    "        b = [0] * n\n",
    "        for i in range(1, n):\n",
    "            if security[i] <= security[i - 1]:\n",
    "                a[i] = a[i - 1] + 1\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if security[i + 1] >= security[i]:\n",
    "                b[i] = b[i + 1] + 1\n",
    "        ans = []\n",
    "        for i in range(time, n - time):\n",
    "            if a[i] >= time and b[i] >= time:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        left = [0]*n\n",
    "        right = [0]*n\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if security[i]<=security[i-1]:\n",
    "                left[i] = left[i-1]+1\n",
    "            if security[n-i-1]<=security[n-i]:\n",
    "                right[n-i-1] = right[n-i]+1\n",
    "        \n",
    "        return [i for i in range(time,n-time) if left[i]>=time and right[i]>=time]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        pre = [0]*n\n",
    "        tail = [0]*n\n",
    "        for i in range(1,n):\n",
    "            if security[i-1]>=security[i]:\n",
    "                pre[i] = pre[i-1]+1\n",
    "            if security[n-i] >= security[n-i-1]:\n",
    "                tail[n-i-1] = tail[n-i]+1\n",
    "        ans = []\n",
    "        for i in range(time,n-time):\n",
    "            if pre[i]>=time and tail[i]>=time:\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        \n",
    "        n = len(security)\n",
    "        pre = [1]*(n+1)\n",
    "        pre[0] = 0\n",
    "        for i in range(1, n):\n",
    "            if security[i]<=security[i-1]:\n",
    "                pre[i+1] = pre[i]+1\n",
    "\n",
    "        post = [1] * (n + 1)\n",
    "        post[-1] = 0\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if security[i]<=security[i+1]:\n",
    "                post[i] = post[i+1]+1\n",
    "        \n",
    "        ans = []\n",
    "        for i in range(time, n-time):\n",
    "            if pre[i+1] >= time+1 and post[i] >= time+1:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        left = [0] * n\n",
    "        right = [0] * n\n",
    "        for i in range(1, n):\n",
    "            if security[i] <= security[i - 1]:\n",
    "                left[i] = left[i - 1] + 1\n",
    "            if security[n - i - 1] <= security[n - i]:\n",
    "                right[n - i - 1] = right[n - i] + 1\n",
    "        return [i for i in range(time, n - time) if left[i] >= time and right[i] >= time]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        left = [0] * n\n",
    "        right = [0] * n\n",
    "        for i in range(1, n):\n",
    "            if security[i] <= security[i - 1]:\n",
    "                left[i] = left[i - 1] + 1\n",
    "            if security[n - i - 1] <= security[n - i]:\n",
    "                right[n - i - 1] = right[n - i] + 1\n",
    "        rst = []\n",
    "        for i in range(time, n - time):\n",
    "            if left[i] >= time and right[i] >= time:\n",
    "                rst.append(i)\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        left = [0] * n\n",
    "        right = [0] * n\n",
    "        for i in range(1, n):\n",
    "            if security[i] <= security[i - 1]:\n",
    "                left[i] = left[i - 1] + 1\n",
    "            if security[n - i - 1] <= security[n - i]:\n",
    "                right[n - i - 1] = right[n - i] + 1\n",
    "        return [i for i in range(time, n - time) if left[i] >= time and right[i] >= time]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        nums = security\n",
    "        answer_list = list()\n",
    "        nums_length = len(nums)\n",
    "   #    # if time == 0:\n",
    "       #     for integer in range(nums_length):\n",
    "        #        answer_list.append(integer)\n",
    "      #      return answer_list\n",
    "        non_increasing_list = [1] * nums_length\n",
    "        non_decreasing_list = [1] * nums_length\n",
    "        for index in range(1, nums_length):\n",
    "            if nums[index] <= nums[index - 1]:\n",
    "                non_decreasing_list[index] = non_decreasing_list[index - 1] + 1\n",
    "        for index in range(nums_length - 2, -1, -1):\n",
    "            if nums[index] <= nums[index + 1]:\n",
    "                non_increasing_list[index] = non_increasing_list[index + 1] + 1\n",
    "        for index in range(time, nums_length - time):\n",
    "            if non_decreasing_list[index] >= time + 1 and non_increasing_list[index] >= time + 1:\n",
    "                answer_list.append(index)\n",
    "        return answer_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        pre, post = [0]*n, [0]*n\n",
    "        for i in range(1, n):\n",
    "            if security[i] <= security[i-1]:\n",
    "                pre[i] = pre[i-1] + 1\n",
    "        \n",
    "        for i in range(n-2, -1, -1):\n",
    "            if security[i] <= security[i+1]:\n",
    "                post[i] = post[i+1] + 1\n",
    "        \n",
    "        res = []\n",
    "        for i in range(time, n-time):\n",
    "            if pre[i] - pre[i-time] == time and post[i] - post[i+time] == time:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        left = [0] * n\n",
    "        right = [0] * n\n",
    "        for i in range(1, n):\n",
    "            if security[i] <= security[i - 1]:\n",
    "                left[i] = left[i - 1] + 1\n",
    "            if security[n - i - 1] <= security[n - i]:\n",
    "                right[n - i - 1] = right[n - i] + 1\n",
    "        return [i for i in range(time, n - time) if left[i] >= time and right[i] >= time]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        left = [0] * n\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if security[i] <= security[i + 1]:\n",
    "                left[i] = left[i + 1] + 1\n",
    "        right = [0] * n\n",
    "        for i in range(1, n):\n",
    "            if security[i] <= security[i - 1]:\n",
    "                right[i] = right[i - 1] + 1\n",
    "        res = []\n",
    "        for i in range(time, n - time):\n",
    "            if left[i] >= time and right[i] >= time:\n",
    "                res.append(i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        l, r = [0] * n, [0] * n\n",
    "        for i in range(1, n):\n",
    "            if security[i] <= security[i-1]:\n",
    "                l[i] = l[i - 1] + 1\n",
    "            else:\n",
    "                l[i] = 0\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if security[i] <= security[i + 1]:\n",
    "                r[i] = r[i + 1] + 1\n",
    "            else:\n",
    "                r[i] = 0\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if l[i] >= time and r[i] >= time:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, nums: List[int], time: int) -> List[int]:\n",
    "        n=len(nums)\n",
    "        a=[0 for i in range(n)]\n",
    "        b=[0 for i in range(n)]\n",
    "        ans=[]\n",
    "        a[0]=1\n",
    "        for i in range(1,n):\n",
    "            if nums[i]<=nums[i-1]:\n",
    "                a[i]=min(a[i-1]+1,time+1)\n",
    "            else:\n",
    "                a[i]=1\n",
    "        b[n-1]=1\n",
    "        for i in range(-2,-n-1,-1):\n",
    "            if nums[i]<=nums[i+1]:\n",
    "                b[i]=min(b[i+1]+1,time+1)\n",
    "            else:\n",
    "                b[i]=1\n",
    "        for i in range(n):\n",
    "            if a[i]==time+1 and b[i]==time+1:\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, nums: List[int], time: int) -> List[int]:\n",
    "        n=len(nums)\n",
    "        a=[0]*n\n",
    "        b=[0]*n\n",
    "        ans=[]\n",
    "        a[0]=1\n",
    "        for i in range(1,n):\n",
    "            if nums[i]<=nums[i-1]:\n",
    "                a[i]=min(a[i-1]+1,time+1)\n",
    "            else:\n",
    "                a[i]=1\n",
    "        b[n-1]=1\n",
    "        for i in range(-2,-n-1,-1):\n",
    "            if nums[i]<=nums[i+1]:\n",
    "                b[i]=min(b[i+1]+1,time+1)\n",
    "            else:\n",
    "                b[i]=1\n",
    "        for i in range(n):\n",
    "            if a[i]==time+1 and b[i]==time+1:\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        left = [0] * n\n",
    "        right = [0] * n\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if security[i-1]>=security[i]:\n",
    "                left[i]=left[i-1]+1\n",
    "        \n",
    "        for i in range(n-2,-1,-1):\n",
    "            if security[i]<=security[i+1]:\n",
    "                right[i]=right[i+1]+1\n",
    "        ans=[]\n",
    "        for i in range(time,n-time):\n",
    "            if left[i] >=time and right[i]>=time:\n",
    "                ans.append(i)\n",
    "        #print(security)\n",
    "        #print(right)\n",
    "        #print(left)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        # 枚举+前后缀\n",
    "        # security = [5,3,3,3,5,6,2], n =7 time = 2 n-time = 5\n",
    "        \n",
    "        \n",
    "        pre = [0]*n\n",
    "        suf = [0]*n\n",
    "        for i in range(1,n):\n",
    "            # pre[i] 从前到后第i天前面非递增的日子\n",
    "            if security[i] <= security[i-1]:\n",
    "                pre[i] = pre[i-1]+1\n",
    "            # suf 从后到前第i天后面非递减的日子\n",
    "            if security[n-i] >= security[n-i-1]:\n",
    "                suf[n-i-1] = suf[n-i]+1\n",
    "        ans = []\n",
    "        # 时间复杂度 O(n)\n",
    "        for i in range(time,n-time):\n",
    "            # 判断i是否是一个适合打劫银行的日子\n",
    "            if pre[i] >= time and suf[i] >= time:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        # 枚举+前后缀\n",
    "        # security = [5,3,3,3,5,6,2], n =7 time = 2 n-time = 5\n",
    "        # pre[i] 从前到后第i天前面非递增的日子\n",
    "        pre = [0]*n\n",
    "        for i in range(1,n):\n",
    "            if security[i] <= security[i-1]:\n",
    "                pre[i] = pre[i-1]+1\n",
    "        # suf 从后到前第i天后面非递减的日子\n",
    "        suf = [0]*n\n",
    "        for i in range(n-1,0,-1):\n",
    "            if security[i] >= security[i-1]:\n",
    "                suf[i-1] = suf[i]+1\n",
    "        ans = []\n",
    "        # 时间复杂度 O(n)\n",
    "        for i in range(time,n-time):\n",
    "            # 判断i是否是一个适合打劫银行的日子\n",
    "            if pre[i] >= time and suf[i] >= time:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        left = [0] * n\n",
    "        cnt = 1\n",
    "        for i in range(1, n):\n",
    "            if security[i] <= security[i - 1]:\n",
    "                left[i] = cnt\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt = 1\n",
    "        right = [0] * n\n",
    "        cnt = 1\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if security[i] <= security[i + 1]:\n",
    "                right[i] = cnt\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt = 1\n",
    "        # print(f'{left}\\n{right}')\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if left[i] >= time and right[i] >= time:\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        left = [0] * n\n",
    "        for i in range(1,n):\n",
    "            if security[i] <= security[i-1]:\n",
    "                left[i] = left[i-1] + 1\n",
    "        right = [0] * n\n",
    "        for j in range(n-2,-1,-1):\n",
    "            if security[j] <= security[j+1]:\n",
    "                right[j] = right[j+1] + 1\n",
    "        # print(left)\n",
    "        # print(right)\n",
    "        output = []\n",
    "        for i in range(n):\n",
    "            if left[i] >= time and right[i] >=time:\n",
    "                output.append(i)\n",
    "        return output\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        \n",
    "        nums = security\n",
    "        answer_list = list()\n",
    "        nums_length = len(nums)\n",
    "        if time == 0:\n",
    "            for integer in range(nums_length):\n",
    "                answer_list.append(integer)\n",
    "            return answer_list\n",
    "        non_increasing_list = [1] * nums_length\n",
    "        non_decreasing_list = [1] * nums_length\n",
    "        for index in range(1, nums_length):\n",
    "            if nums[index] <= nums[index - 1]:\n",
    "                non_decreasing_list[index] = non_decreasing_list[index - 1] + 1\n",
    "        for index in range(nums_length - 2, -1, -1):\n",
    "            if nums[index] <= nums[index + 1]:\n",
    "                non_increasing_list[index] = non_increasing_list[index + 1] + 1\n",
    "        for index in range(time, nums_length - time):\n",
    "            if non_decreasing_list[index] >= time + 1 and non_increasing_list[index] >= time + 1:\n",
    "                answer_list.append(index)\n",
    "        return answer_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n=len(security)\n",
    "        if time==0:\n",
    "            return list(range(n))\n",
    "        up = [0]*n\n",
    "        down =[0]*n\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if security[i]<=security[i-1]:\n",
    "                up[i]=up[i-1]+1\n",
    "        \n",
    "        for i in range(n-2,-1,-1):\n",
    "            if security[i]<=security[i+1]:\n",
    "                down[i]=down[i+1]+1\n",
    "        # print(time,n-time)\n",
    "        ans = []\n",
    "        return [i for i in range(n) if up[i] >= time and down[i] >= time]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n=len(security)\n",
    "        if time==0:\n",
    "            return [i for i in range(n)]\n",
    "        dp=[False for _ in range(n)]\n",
    "        dp1=[0]*n\n",
    "        for i in range(1,n):\n",
    "            if security[i]<=security[i-1]:\n",
    "                dp1[i]=dp1[i-1]+1\n",
    "            else:\n",
    "                dp1[i]=0\n",
    "        dp2=[0]*n\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if security[i]<=security[i+1]:\n",
    "                dp2[i]=dp2[i+1]+1\n",
    "            else:\n",
    "                dp2[i]=0\n",
    "        for i in range(time,n-time):\n",
    "            if dp1[i]>=time and dp2[i]>=time:\n",
    "                dp[i]=True\n",
    "        return [ i for i in range(n) if dp[i]]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n=len(security)\n",
    "        if time==0:\n",
    "            return [i for i in range(n)]\n",
    "        dp=[False for _ in range(n)]\n",
    "        dp1=[0]*n\n",
    "        for i in range(1,n):\n",
    "            if security[i]<=security[i-1]:\n",
    "                dp1[i]=dp1[i-1]+1\n",
    "            else:\n",
    "                dp1[i]=0\n",
    "        dp2=[0]*n\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if security[i]<=security[i+1]:\n",
    "                dp2[i]=dp2[i+1]+1\n",
    "            else:\n",
    "                dp2[i]=0\n",
    "        for i in range(time,n-time):\n",
    "            if dp1[i]>=time and dp2[i]>=time:\n",
    "                dp[i]=True\n",
    "        return [ i for i in range(n) if dp[i]]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n=len(security)\n",
    "        if time==0:\n",
    "            return [i for i in range(n)]\n",
    "        dp=[False for _ in range(n)]\n",
    "        dp1=[0]*n\n",
    "        for i in range(1,n):\n",
    "            if security[i]<=security[i-1]:\n",
    "                dp1[i]=dp1[i-1]+1\n",
    "            else:\n",
    "                dp1[i]=0\n",
    "        dp2=[0]*n\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if security[i]<=security[i+1]:\n",
    "                dp2[i]=dp2[i+1]+1\n",
    "            else:\n",
    "                dp2[i]=0\n",
    "        for i in range(time,n-time):\n",
    "            if dp1[i]>=time and dp2[i]>=time:\n",
    "                dp[i]=True\n",
    "        return [ i for i in range(n) if dp[i]]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        # 求左右前缀和\n",
    "        n = len(security)\n",
    "        preSum, sufSum = [0]*(n+1), [0]*(n+1)\n",
    "        for i in range(1, n):\n",
    "            preSum[i] = preSum[i-1]+1 if security[i] <= security[i-1] else 0\n",
    "            sufSum[n-i] = sufSum[n-i+1]+1 if security[n-i-1] <= security[n-i] else 0\n",
    "        \n",
    "        print(preSum, sufSum)\n",
    "        ret = []\n",
    "        for i in range(time, n-time):\n",
    "            if preSum[i] >= time and sufSum[i+1] >= time:\n",
    "                ret.append(i)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        increasing = [0 for _ in range(len(security))]\n",
    "        decreasing = [0 for _ in range(len(security))]\n",
    "        \n",
    "        for idx in range(1, len(security)):\n",
    "            if security[idx-1] >= security[idx]:\n",
    "                increasing[idx] = increasing[idx-1] + 1\n",
    "            else:\n",
    "                increasing[idx] = 0\n",
    "        \n",
    "        for idx in range(len(security)-2, -1, -1):\n",
    "            if security[idx] <= security[idx+1]:\n",
    "                decreasing[idx] = decreasing[idx+1] + 1\n",
    "            else:\n",
    "                decreasing[idx] = 0\n",
    "        res = []       \n",
    "        for idx in range(len(security)):\n",
    "            if idx - time >= 0 and len(security) -1 - idx >= time and increasing[idx]>= time and decreasing[idx]>= time:\n",
    "                res.append(idx)\n",
    "                \n",
    "        print(increasing)\n",
    "        print(decreasing)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        # 枚举+前后缀\n",
    "        # security = [5,3,3,3,5,6,2], n =7 time = 2 n-time = 5\n",
    "        # pre[i] 从前到后第i天前面非递增的日子\n",
    "        pre = [1]*n\n",
    "        for i in range(1,n):\n",
    "            if security[i] <= security[i-1]:\n",
    "                pre[i] = pre[i-1]+1\n",
    "        print(pre)\n",
    "        # suf 从后到前第i天后面非递减的日子\n",
    "        suf = [1]*n\n",
    "        for i in range(n-1,0,-1):\n",
    "            if security[i] >= security[i-1]:\n",
    "                suf[i-1] = suf[i]+1\n",
    "        print(suf)\n",
    "        ans = []\n",
    "        # 时间复杂度 O(n)\n",
    "        for i in range(time,n-time):\n",
    "            # 判断i是否是一个适合打劫银行的日子\n",
    "            if pre[i] >= time+1 and suf[i] >= time+1:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "\n",
    "        ans = []\n",
    "        # 中间节点为谷底\n",
    "\n",
    "        # 分别使用两个数组存储当前位置i，从左向右递减的个数，从右向左递增的个数\n",
    "        l = len(security)\n",
    "        left = [1]*l\n",
    "        right = [1]*l\n",
    "\n",
    "        for i,ch in enumerate(security):\n",
    "            if i==0:\n",
    "                continue\n",
    "            else:\n",
    "                if security[i]<=security[i-1]:\n",
    "                    left[i] = left[i-1]+1\n",
    "        \n",
    "        temp = security[::-1]\n",
    "        for i,ch in enumerate(temp):\n",
    "            if i==0:\n",
    "                continue\n",
    "            else:\n",
    "                if temp[i]<=temp[i-1]:\n",
    "                    right[i] = right[i-1]+1\n",
    "\n",
    "        right = right[::-1]\n",
    "\n",
    "        for i in range(l):\n",
    "            if left[i]>time and right[i]>time:\n",
    "                ans.append(i)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:\n",
    "        n = len(security)\n",
    "        left = [0] * n\n",
    "        cnt = 1\n",
    "        for i in range(1, n):\n",
    "            if security[i] <= security[i - 1]:\n",
    "                left[i] = cnt\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt = 1\n",
    "        right = [0] * n\n",
    "        cnt = 1\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if security[i] <= security[i + 1]:\n",
    "                right[i] = cnt\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt = 1\n",
    "        print(f'{left}\\n{right}')\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if left[i] >= time and right[i] >= time:\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
